#include <iostream>
#include <stdio.h>
using namespace std;

int GedMidi(int* a,int left,int right)
{
    int mid = left + (right-left)/2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }else
    {
        if(a[mid] > a[right])
        {
            return mid;
        }else if(a[left] < a[right])
        {
            return left;
        }else 
        {
            return right;
        }
    }
}

void QuickSork(int arr[],int left,int right)
{
    if(left >= right)
        return;
    
    int begin = left;
    int end = right;
    int midi = GedMidi(arr,left,right);
    swap(arr[left],arr[midi]);
    int cur = left+1;
    int key = arr[left];
    while(cur <= right)
    {
        if(arr[cur] < key)
        {
            swap(arr[left],arr[cur]);
            cur++;
            left++;
        }else if(arr[cur] > key)
        {
            swap(arr[cur],arr[right]);
            --right;
        }else 
        {
            ++cur;
        }
    }

    QuickSork(arr,begin,left-1);
    QuickSork(arr,right+1,end);

}


int main()
{
    int arr[10] = {6,2,4,3,1,7,5,8,9};
    QuickSork(arr,0,sizeof(arr)/sizeof(int)-1);

    for(auto e : arr)
    {
        cout << e << " "<<endl;
    }

    return 0;
}